1. Field of the Invention
The present invention relates to facsimile transmission systems, and more particularly to data compression techniques useful in reducing the amount of data transmitted during the scanning of a document.
2. Description of the Prior Art
In the transmission of document images over long distances, digital techniques based on a threshold black/white discrimination have been practiced in the past. Such technique has been found particularly useful when communication is made over standard voice frequency telephone networks. Telephone networks are generally quite limited in bandwidth and fidelity therefore transmission of linear signals similar to that practiced in television image transmission, is often less than adequate.
Accordingly, many prior art techniques have been developed for breaking down the document image into a scan-by-scan series of discrete picture elements or, as commonly referred to "pixels", each pixel indicating, in terms of binary code, whether the local reflectivity of the document is below or above a certain threshold. Thus, many very fine pixels are transmitted and reconstruct at the receiver the document image. The volume of data produced by this scanning technique is necessarily high for any acceptable level of fidelity and many bandwidth compression systems have been developed in the past for compressing such data.
A typical prior art technique for data compression of digitized facsimile images is a technique commonly referred to as "run-length compression". This technique utilizes, to some advantage, the fact that if an image is present on the document, the distinct characteristics thereof will normally be much larger than any singular pixel. Thus, in a scan-by-scan transmission a series of white pixels is typically converted to a count code, like a binary series count code, which is then terminated by a transition code to the black reflectivity level. The black level can then be similarly coded in terms of pixel count until a full scan line is thus completed. This technique, while quite useful for its purpose, is still less than optimal since, the largest compression factor which can be achieved is that of a serial to binary series conversion. To augment such compression schemes, there have been devised in the past, additional techniques which convert the binary code to some other base as for example, a base of six, and thereby exchange the length of transmission for phase modulation. Even this latter technique, however, has been found also limiting particularly when the cost of long distance telephone communication is considered.
Both of the above techniques, however, do not discriminate between character and background. Since in most documents background represents the bulk of the data transmitted the above prior art techniques which compress the data in serial form necessarily transmit background at the same level of compression. Thus, depending on the number of black and white intervals within one particular image series or scan series, there is a minimum level of data compression which can be achieved by these techniques.
Of the several two-dimensional compression techniques disclosed in the prior art, most rely on arbitrary sub-arrays achieved by steps like folding, wherein a two-dimensional image is divided into elemental areas and is successively folded upon itself. During each folding process, the data on one side of the fold is correlated with the data in the other side of the fold to determine non-similarity. In this latter case, the process of correlating folded images involves relatively complicated logic operations. Thus, there are no data compression systems presently known which are particularly suited for a scan-by-scan facsimile device and which subsequent to scanning reduce the data bulk according to its character.